from typing import List
#双向链表
class MyListNode:

    def __init__(self, val):
        self.val = val
        self.pre = None
        self.next = None


class MyLinkedList:

    def __init__(self):
        self.head = MyListNode(-1)
        self.tail = MyListNode(-1)
        self.head.next = self.tail
        self.tail.pre = self.head
        self.size = 0

    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1

        dummy = self.getNode(index)
        return dummy.val

    def addAtHead(self, val: int) -> None:
        self.addNode(self.head, self.head.next, val)

    def addAtTail(self, val: int) -> None:
        self.addNode(self.tail.pre, self.tail, val)

    def addAtIndex(self, index: int, val: int) -> None:
        if index > self.size:
            return
        if index < 0:
            index = 0
        node = self.getNode(index)
        self.addNode(node.pre, node, val)

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size:
            return
        node = self.getNode(index)
        node.pre.next = node.next
        node.next.pre = node.pre
        self.size -= 1

    def getNode(self, index: int) -> MyListNode:
        if index < self.size // 2:
            dummy = self.head
            for i in range(index + 1):
                dummy = dummy.next
        else:
            dummy = self.tail
            for i in range(self.size - index):
                dummy = dummy.pre
        return dummy

    def addNode(self, first: MyListNode, second: MyListNode, val: int) -> None:
        node = MyListNode(val)
        node.next = second
        second.pre = node
        first.next = node
        node.pre = first
        self.size += 1